Charles Dicken’s classic character Ebenezer Scrooge may well be the most greedy person ever, fictional or real. Recall that Scrooge never considered the past or future. Each day his only drive was to greedily grab as much gold as he could. After the Ghost of Christmas Past reminded him of the past and the Ghost of Christmas Future warned him of the future, he changed his greedy ways.
A greedy algorithm proceeds in the same way as Scrooge did. That is, it grabs data items in sequence, each time taking the one that is deemed best according to some criterion, without regard for the choices it has made before or will make in the future.
찰스 디킨스의 소설에 나오는 스크루지라는 인물을 예로들어 탐욕적인 방법과 연결시켜 설명하고 있다. 탐욕적인 방법은 과거나 미래를 고려하지 않고, 현재의 그 순간에서 최선을 결정한다는 점에서 스크루지의 방법과 같다.
The Greedy Approach
Like dynamic programming, greedy algorithms are often used to solve optimization problems. However, the greedy approach is more straightforward. In dynamic programming, a recursive property is used to divide an instance into smaller instances. In the greedy approach, there is no division into smaller instances. A greedy algorithm arrives at a solution by making a sequence of choices, each of which simply looks the best at the moment. That is, each choice is locally optimal. The hope is that a globally optimal solution will be obtained, but this is not always the case. For a given algorithm, we must determine whether the solution is always optimal.
A selection procedure chooses the next item to add to the set. The selection is performed according to a greedy criterion that satisfies some locally optimal consideration at the time.
A feasibility check determines if the new set is feasible by checking whether it is possible to complete this set in such a way as to give a solution to the instance.
A solution check determines whether the new set constitutes a solution to the instance.
탐욕 알고리즘은 동적계획법과 마찬가지로 종종 최적화 문제를 해결하는데 사용된다. 이 방법은 결정을 해야 할 때마다 그 순간에 가장 좋다고 생되는 것을 해답으로 선택함으로써 최종적인 해답에 도달한다.
그 순간의 선택은 그 당시에는 최적이다(locally optimal). 하지만 최적이라고 생각했던 해답들을 모아 최종적인 해답을 만들었다고 해서, 그 해답이 궁극적으로 최적이라는 보장은 없다(globally optimal). 따라서 탐욕 알고리즘이 항상 최적의 해답을 주는지를 반드시 검증해야 한다.